#include <iostream>
#include <math.h>
#include "tdeapporo.h"
#include "tvectorporo.h"

using namespace std;


TDeapPoro::TDeapPoro()
{
    posicion = 1;
}
TDeapPoro::TDeapPoro(const TDeapPoro & tdp)
{
    if(!tdp.EsVacio())
    {
        v=tdp.v;
        posicion=tdp.posicion;
    }
}
TDeapPoro::~TDeapPoro()
{
    posicion=0;
}

TDeapPoro & TDeapPoro::operator=(const TDeapPoro & tdp)
{
    if(this!=&tdp)
    {
        v.~TVectorPoro();
        v=tdp.v;
        posicion=tdp.posicion;
    }

    return *this;
}
bool TDeapPoro::operator==(const TDeapPoro & tdp)
{
    bool iguales = true;
    int n = 2;

    while(iguales == true && n < v.Longitud() && n < tdp.v.Longitud())
    {
        if(v[n] != tdp.v[n])
        {
            iguales = false;
        }
        n++;
    }

    return iguales;
}
bool TDeapPoro::operator!=(const TDeapPoro & tdp)
{
    bool distintos = true;

    if((*this) == tdp)
    {
        distintos = false;
    }

    return distintos;
}
bool TDeapPoro::EsVacio() const
{
    bool vacio = false;

    if(v.Longitud() == 0)
    {
        vacio = true;
    }

    return vacio;
}
bool TDeapPoro::Insertar(const TPoro &c)
{
    bool insertado = false;

    if(EsVacio())
    {
        insertado=true;
        TPoro vacio;
        v.Redimensionar(10);
        v[posicion] = vacio;
        posicion++;
        v[posicion]=c;
        posicion++;
        insertado=true;
    }
    else
    {
        for(int i=2; i<posicion && !insertado; i++)if(v[i].Volumen()==c.Volumen())insertado=true;
    }
    if(insertado)
    {
        insertado=false;
    }
    else
    {
        if(v.Longitud()==posicion)v.Redimensionar(v.Longitud()+10);
        int ElementoInsertar=posicion;

        int NivelActual=log2(ElementoInsertar);
        int ElementosNivelAnterior=pow(2, (NivelActual-1));
        int ElementosNivelActual=pow(2, (NivelActual));
        int MitadNivelActual=ElementosNivelActual+ElementosNivelAnterior;
        int Simetrico;

        if(ElementoInsertar<MitadNivelActual)
        {
            //MINHEAP
            Simetrico=ElementoInsertar+ElementosNivelAnterior;
            Simetrico/=2;
            TPoro *PSimetrico=&v[Simetrico];
            const TPoro *PInsertar=&c;
            if(PSimetrico->Volumen()<PInsertar->Volumen())
            {
                v[ElementoInsertar]=v[Simetrico];
                v[Simetrico]=c;

                ElementoInsertar=Simetrico;
                NivelActual--;
                ElementosNivelActual/=2;
                ElementosNivelAnterior/=2;
                MitadNivelActual=ElementosNivelActual+ElementosNivelAnterior;
            }
            else
            {
                v[ElementoInsertar]=c;
            }
        }
        else
        {
            //MAXHEAP
            Simetrico=ElementoInsertar-ElementosNivelAnterior;
            TPoro *PSimetrico=&v[Simetrico];
            const TPoro *PInsertar=&c;
            if(PSimetrico->Volumen()>PInsertar->Volumen())
            {
                v[ElementoInsertar]=v[Simetrico];
                v[Simetrico]=c;

                ElementoInsertar=Simetrico;
            }
            else
            {
                v[ElementoInsertar]=c;
            }
        }
        posicion++;

        if(ElementoInsertar<MitadNivelActual)
        {
            //MINHEAP
            TPoro *Padre=&v[ElementoInsertar/2];
            const TPoro *PInsertar=&c;
            while(Padre->Volumen()>PInsertar->Volumen() && ElementoInsertar>2)
            {
                v[ElementoInsertar]=*Padre;
                v[ElementoInsertar/2]=c;
                ElementoInsertar/=2;
                Padre=&v[ElementoInsertar/2];
            }
        }
        else
        {
            //MAXHEAP
            TPoro *Padre=&v[ElementoInsertar/2];
            const TPoro *PInsertar=&c;
            while(Padre->Volumen()<PInsertar->Volumen() && ElementoInsertar>3)
            {
                v[ElementoInsertar]=*Padre;
                v[ElementoInsertar/2]=c;
                ElementoInsertar/=2;
                Padre=&v[ElementoInsertar/2];
            }
        }
        insertado=true;
    }
    return insertado;
}
bool TDeapPoro::BorrarMax()
{
    bool borrado = false;

    int ElementoMover=2;
    if(posicion-2>ElementoMover)
    {
        TPoro temporal;
        posicion--;
        ElementoMover++;
        v[ElementoMover]=v[posicion];
        v[posicion]=v[1];
        int NuevaPosicion=2*ElementoMover;

        TPoro* PNuevaPosicion1=NULL;
        TPoro* PNuevaPosicion2=NULL;
        TPoro* PMover=NULL;

        bool FinUndir=false;
        while(!FinUndir)
        {
            PNuevaPosicion1=&v[NuevaPosicion];
            PNuevaPosicion2=&v[NuevaPosicion+1];
            PMover=&v[ElementoMover];
            if(!(NuevaPosicion+1<posicion && PNuevaPosicion1->Volumen()>PNuevaPosicion2->Volumen()) && (NuevaPosicion<posicion && PNuevaPosicion1->Volumen()>PMover->Volumen()))
            {
                temporal=v[ElementoMover];
                v[ElementoMover]=v[NuevaPosicion];
                v[NuevaPosicion]=temporal;
                ElementoMover=NuevaPosicion;
                NuevaPosicion*=2;
            }
            else if(NuevaPosicion+1<posicion && PNuevaPosicion2->Volumen()>PMover->Volumen())
            {
                temporal=v[ElementoMover];
                v[ElementoMover]=v[NuevaPosicion+1];
                v[NuevaPosicion+1]=temporal;
                ElementoMover=NuevaPosicion+1;
                NuevaPosicion*=2;
                NuevaPosicion++;
            }
            else
            {
                FinUndir=true;
            }
        }

        int simetrico=ElementoMover+pow(2,log2(ElementoMover)-1);
        if(simetrico>posicion)simetrico/=2;

        TPoro* PSimetrico=&v[simetrico];
        PMover=&v[ElementoMover];

        if(posicion>simetrico && PSimetrico->Volumen()>PMover->Volumen())
        {
            temporal=v[ElementoMover];
            v[ElementoMover]=v[simetrico];
            v[simetrico]=temporal;

            ElementoMover=simetrico;
            NuevaPosicion=ElementoMover/2;
            bool FinSubir=false;

            TPoro* PNuevaPosicion=NULL;

            while(NuevaPosicion>1 && !FinSubir)
            {
                PNuevaPosicion=&v[NuevaPosicion];
                PMover=&v[ElementoMover];
                if(NuevaPosicion<posicion && PNuevaPosicion->Volumen()>PMover->Volumen())
                {
                    temporal=v[ElementoMover];
                    v[ElementoMover]=v[NuevaPosicion];
                    v[NuevaPosicion]=temporal;
                    ElementoMover=NuevaPosicion;
                    NuevaPosicion/=2;
                }
                else
                {
                    FinSubir=true;
                }
            }
        }
    }
    else if(posicion-1==3)
    {
        posicion--;
        v[3]=v[1];
    }
    else
    {
        posicion--;
        v[2]=v[1];
    }
    if(v.Longitud()/10 != (((v.Cantidad()+1)/10)+1))v.Redimensionar(v.Longitud()-10);
    return borrado;
}
bool TDeapPoro::BorrarMin()
{
    bool borrado = false;

    int ElementoMover=1;
    if(posicion-2>ElementoMover)
    {
        TPoro temporal;
        posicion--;
        ElementoMover++;
        v[ElementoMover]=v[posicion];
        v[posicion]=v[1];
        int NuevaPosicion=2*ElementoMover;
        bool FinUndir=false;

        TPoro* PNuevaPosicion1=NULL;
        TPoro* PNuevaPosicion2=NULL;
        TPoro* PMover=&v[ElementoMover];

        while(!FinUndir)
        {
            PNuevaPosicion1=&v[NuevaPosicion];
            PNuevaPosicion2=&v[NuevaPosicion+1];
            PMover=&v[ElementoMover];
            if(!(NuevaPosicion+1<posicion && PNuevaPosicion1->Volumen()>PNuevaPosicion2->Volumen()) && (NuevaPosicion<posicion && PNuevaPosicion1->Volumen()<PMover->Volumen()))
            {//Comentario cualquiera
                temporal=v[ElementoMover];
                v[ElementoMover]=v[NuevaPosicion];
                v[NuevaPosicion]=temporal;
                ElementoMover=NuevaPosicion;
                NuevaPosicion*=2;
            }
            else if(NuevaPosicion+1<posicion && PNuevaPosicion2->Volumen()<PMover->Volumen())
            {
                temporal=v[ElementoMover];
                v[ElementoMover]=v[NuevaPosicion+1];
                v[NuevaPosicion+1]=temporal;
                ElementoMover=NuevaPosicion+1;
                NuevaPosicion*=2;
                NuevaPosicion++;
            }
            else
            {
                FinUndir=true;
            }
        }
        int simetrico=ElementoMover+pow(2,log2(ElementoMover)-1);
        if(simetrico>posicion)simetrico/=2;

        TPoro* PSimetrico=&v[simetrico];
        PMover=&v[ElementoMover];

        if(posicion>simetrico && PSimetrico->Volumen()<PMover->Volumen())
        {
            temporal=v[ElementoMover];
            v[ElementoMover]=v[simetrico];
            v[simetrico]=temporal;

            ElementoMover=simetrico;
            NuevaPosicion=ElementoMover/2;
            bool FinSubir=false;

            TPoro* PNuevaPosicion=NULL;

            while(NuevaPosicion>1 &&!FinSubir)
            {
                PNuevaPosicion=&v[NuevaPosicion];
                PMover=&v[ElementoMover];
                if(NuevaPosicion<posicion && PNuevaPosicion->Volumen()<PMover->Volumen())
                {
                    temporal=v[ElementoMover];
                    v[ElementoMover]=v[NuevaPosicion];
                    v[NuevaPosicion]=temporal;
                    ElementoMover=NuevaPosicion;
                    NuevaPosicion/=2;
                }
                else
                {
                    FinSubir=true;
                }
            }
        }
    }
    else
    {
        posicion--;
        v[2]=v[1];
    }
    if(v.Longitud()/10 != ((v.Cantidad()+1)/10)+1)v.Redimensionar(v.Longitud()-10);
    return borrado;
}
TPoro TDeapPoro::Max() const
{
    TPoro maximo;
    if(v.Cantidad()+1>=3)maximo=v[3];
    return maximo;
}
TPoro TDeapPoro::Min() const
{
    TPoro minimo;
    if(v.Cantidad()+1>=2)minimo=v[2];
    return minimo;
}
int TDeapPoro::Altura() const
{
    int altura = 0;
    altura=log2(posicion)+1;
    return altura;
}
int TDeapPoro::Nodos() const
{
    int cantidad = posicion - 1;
    return cantidad;
}
TVectorPoro TDeapPoro::InordenAux(int i)const
{
    TVectorPoro inorden;

    int PosicionHijos=2*i;
    TVectorPoro Raiz(1);
    TVectorPoro Derecha;
    TVectorPoro Izquierda;
    Raiz[1]=v[i];
    if(PosicionHijos<=posicion)Derecha=InordenAux(PosicionHijos);
    if(++PosicionHijos<=posicion)Izquierda=InordenAux(PosicionHijos);
    int tamanyo=Raiz.Cantidad()+Derecha.Cantidad()+Izquierda.Cantidad();
    if(i=1)tamanyo++;
    inorden.Redimensionar(tamanyo);

    int x=0;
    for(int j=1; j<Derecha.Cantidad()+1; j++)inorden[++x]=Derecha[j];
    inorden[++x]=Raiz[1];
    for(int j=1; j<Izquierda.Cantidad()+1; j++)inorden[++x]=Izquierda[j];

    return inorden;
}
TVectorPoro TDeapPoro::PreordenAux(int i)const
{
    TVectorPoro preorden;

    int PosicionHijos=2*i;
    TVectorPoro Raiz(1);
    TVectorPoro Derecha;
    TVectorPoro Izquierda;
    Raiz[1]=v[i];
    if(PosicionHijos<=posicion)Derecha=PreordenAux(PosicionHijos);
    if(++PosicionHijos<=posicion)Izquierda=PreordenAux(PosicionHijos);
    int tamanyo=Raiz.Cantidad()+Derecha.Cantidad()+Izquierda.Cantidad();
    if(i=1)tamanyo++;
    preorden.Redimensionar(tamanyo);

    int x=0;
    preorden[++x]=Raiz[1];
    for(int j=1; j<Derecha.Cantidad()+1; j++)preorden[++x]=Derecha[j];
    for(int j=1; j<Izquierda.Cantidad()+1; j++)preorden[++x]=Izquierda[j];

    return preorden;
}
TVectorPoro TDeapPoro::PostordenAux(int i)const
{
    TVectorPoro postorden;

    int PosicionHijos=2*i;
    TVectorPoro Raiz(1);
    TVectorPoro Derecha;
    TVectorPoro Izquierda;
    Raiz[1]=v[i];
    if(PosicionHijos<=posicion)Derecha=PostordenAux(PosicionHijos);
    if(++PosicionHijos<=posicion)Izquierda=PostordenAux(PosicionHijos);
    int tamanyo=Raiz.Cantidad()+Derecha.Cantidad()+Izquierda.Cantidad();
    if(i=1)tamanyo++;
    postorden.Redimensionar(tamanyo);

    int x=0;
    for(int j=1; j<Derecha.Cantidad()+1; j++)postorden[++x]=Derecha[j];
    for(int j=1; j<Izquierda.Cantidad()+1; j++)postorden[++x]=Izquierda[j];
    postorden[++x]=Raiz[1];

    return postorden;
}
TVectorPoro TDeapPoro::Inorden()const
{
    TVectorPoro inorden;

    inorden=InordenAux(1);

    return inorden;
}
TVectorPoro TDeapPoro::Preorden()const
{
    TVectorPoro preorden;

    preorden=PreordenAux(1);

    return preorden;
}
TVectorPoro TDeapPoro::Postorden()const
{
    TVectorPoro postorden;

    postorden=PostordenAux(1);

    return postorden;
}
TVectorPoro TDeapPoro::Niveles()const
{
    TVectorPoro niveles(v);
    niveles.Redimensionar(niveles.Cantidad()+1);
    return niveles;
}


ostream& operator<<(ostream &os, const TDeapPoro &TDeap)
{
   os << TDeap.Niveles();
   return os;
}
